class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        if(nums[right] < target) // 找不到就尾插
        {
            return right + 1;
        }
        while(left < right) // 找不到target就找一个比target大的值，插入到它的前面
        {
            int mid = left + (right - left) / 2; // 根据上面注释用二分中找左端点的套路
            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
        /*auto it = lower_bound(nums.begin(), nums.end(), target);
        return it - nums.begin();
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();*/
    }
};